package com.zzy.sort;

import static com.zzy.sort.JZ45MinNumber.exch;

/**
 * 169. 多数元素
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * 示例 1：输入：nums = [3,2,3]输出：3
 * 示例 2：输入：nums = [2,2,1,1,1,2,2]输出：2
 */
public class LC146MajorityElement {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 1, 1, 1, 2, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5, 5};
        System.out.println(majorityElement(nums));
    }

    private static int majorityElement(int[] nums) {
        //先快排在取中位数
//        quickSort(nums, 0, nums.length - 1);
//        return nums[nums.length / 2];

        //摩尔投票
        int can = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == can) count++;
            else {
                if (count > 0) count--;
                else {
                    can = nums[i];
                    count = 1;
                }
            }
        }
        return can;
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return;
        int mid = partition(arr, start, end);
        quickSort(arr, start, mid - 1);
        quickSort(arr, mid + 1, end);
    }

    private static int partition(int[] arr, int start, int end) {
        int left = start;
        int right = end + 1;
        int pivot = arr[start];
        while (true) {
            while (++left <= end && arr[left] < pivot) ;
            while (--right >= start && arr[right] > pivot) ;
            if (left > right) {
                break;
            }
            exch(arr, left, right);
        }
        exch(arr, start, right);
        return right;
    }


}
